home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15032 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.2 KB
  1. Path: cisu2.jsc.nasa.gov!usenet
  2. From: "James P. Williams" <williams>
  3. Newsgroups: comp.lang.c++
  4. Subject: Sorting Algorithm Using Iterators
  5. Date: 3 Apr 1996 05:50:26 GMT
  6. Organization: NASA/Johnson Space Center
  7. Message-ID: <4jt3j2$cbn@cisu2.jsc.nasa.gov>
  8. NNTP-Posting-Host: lego.jsc.nasa.gov
  9. Mime-Version: 1.0
  10. Content-Type: text/plain; charset=us-ascii
  11. Content-Transfer-Encoding: 7bit
  12. X-Mailer: Mozilla 1.1N (X11; I; IRIX 5.2 IP12)
  13. X-URL: news:comp.lang.c++
  14.  
  15. Does anyone know of an implementation of Quicksort or Heap Sort that accesses
  16. the underlying container using iterators only?  I have a class hierarchy of
  17. iterators, each intended to be used with a particular container class.  I would
  18. like to write a single sorting function that can be used on any type of
  19. container that has an associated iterator class.  It would be best if it
  20. required iteration in only one direction.
  21.  
  22. The implementations with which I am familiar use array indexing (random access)
  23. to access the contained items.  However, iterators for some classes, e.g.,
  24. linked lists, are cannot provide random access in constant time, and are more
  25. appropriate for sequential accesses.
  26.  
  27. I believe the sorting implementation in the STL accepts only iterators that
  28. support random access.
  29.  
  30.  
  31. Thanks,
  32.  
  33. Jim
  34.  
  35.